#include "./hash-map_linked.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

LinkedHashMap *createLinkHashMap()
{
	LinkedHashMap *map = (LinkedHashMap *)malloc(sizeof(LinkedHashMap));
	map->count = 0;
	// 初始化结点空间，哈希表中的每个空间存放一个头结点，头结点存放第一个没有冲突的值，若有冲突的值则向该结点后面追加
	int i;
	for (i = 0; i < MAX_LINK_HASH_SIZE; i++)
	{
		strcpy(map->nodes[i].key, NULL_KEY);
		strcpy(map->nodes[i].value, NULL_KEY);
		map->nodes[i].next = NULL;
	}
}

int hash(char key[])
{
	// 计算字符串字符总和
	int total = 0;
	char *p;
	for (p = key; *p != '\0'; p++)
	{
		total += *p;
	}
	return total % MAX_LINK_HASH_SIZE;
}

void putLinkHashMap(LinkedHashMap *map, char key[], char value[])
{
	// 先找到对应的地址位置的结点
	HNode *pointer = &map->nodes[hash(key)];
	// 结点没有存放元素（为空键）则直接存入
	if (strcmp(pointer->key, NULL_KEY) == 0)
	{
		strcpy(pointer->key, key);
		strcpy(pointer->value, value);
		map->count++;
		return;
	}
	// 否则发生冲突，在这个结点后面追加结点
	HNode *newNode = (HNode *)malloc(sizeof(HNode));
	strcpy(newNode->key, key);
	strcpy(newNode->value, value);
	newNode->next = NULL;
	// 头插法，减少查找尾结点的时间
	newNode->next = pointer->next;
	pointer->next = newNode;
	map->count++;
}

char *getLinkHashMap(LinkedHashMap *map, char key[])
{
	// 先找到对应的地址位置的结点
	HNode *pointer = &map->nodes[hash(key)];
	// 若直接映射到空键则键不存在
	if (strcmp(pointer->key, NULL_KEY) == 0)
	{
		return NULL;
	}
	// 如果找到的不是这个键，则往后查找
	while (strcmp(pointer->key, key) != 0)
	{
		pointer = pointer->next;
		// 如果往后找发现为空，说明该键不存在
		if (pointer == NULL)
		{
			return NULL;
		}
	}
	// 此时找到了键，返回该键所在的结点的值
	return pointer->value;
}

void deleteLinkHashMap(LinkedHashMap *map, char key[])
{
	// 先找到对应的地址位置的结点
	HNode *pointer = &map->nodes[hash(key)], *dNode;
	// 若直接映射到空键则键不存在
	if (map->count == 0 || strcmp(pointer->key, NULL_KEY) == 0)
	{
		return;
	}
	// 若直接映射到头，则直接删除
	if (strcmp(pointer->key, key) == 0)
	{
		strcpy(pointer->key, NULL_KEY);
		map->count--;
		return;
	}
	// 否则，找到对应键的前一结点
	while (pointer->next != NULL && strcmp(pointer->next->key, key) != 0)
	{
		pointer = pointer->next;
	}
	// 如果后一个为空说明键不存在
	if (pointer->next == NULL)
	{
		return;
	}
	// 否则说明找到了，进行结点删除
	dNode = pointer->next;
	pointer->next = pointer->next->next;
	free(dNode);
	map->count--;
}